The present invention relates to partial scan testing of integrated circuits and specifically to a method of computing minimum-cost feedback-vertex sets for a graph of an integrated circuit for use in selecting memory elements for partial scan testing.
Partial scan testing of integrated circuits is becoming a more widespread method. The method provides comparable ease of testing as full scan testing at a fraction of the cost. The main issue when using partial scan testing is the selection of the proper memory elements, i.e. latches or flip-flops, comprising the scan chain.
Testing of sequential circuits is recognized as a key problem in the design and manufacture of integrated circuits. Unfortunately, it is a problem that has not yet been solved to the desired level of satisfaction. Scan insertion is a widely used design-for-testability approach to simplifying the test generation and test application problems for sequential circuits. Unfortunately, making a flip-flop scannable introduces area and performance penalties in the design. These penalties make scanning all flip-flops infeasible in a large number of situations. It has also been suggested in the prior art that an intelligent choice of a subset of flip-flops for scan insertion can lead to significant improvement in the testability of the design, thereby making it possible to realize the design-for-testability goal without significant area or performance penalties. This approach has come to be known as partial scan testing. Given a limited number of flip-flops available for scan insertion, the method used for flip-flop selection is of utmost importance in partial scan testing since it determines the testability of the final circuit. The present invention concerns a method for use in flip-flop selection.
Previous work in this regard has concentrated on applying the knowledge of circuit topology to flip-flop selection. It has been recognized in the prior art that the lengths of the input sequences required to test the faults are a direct measure of the testability of the circuit. In general, the longer the test sequences, the greater are the times required for test generation and test application. Feedback latches in sequential circuits are the primary reason for long test sequences. Recognizing that, a flip-flop selection method that operated by making the circuit maximally feedback free was proposed by Cheng and Agrawal in an article entitled "An Economical Scan Design for Sequential Logic Test Generation" in the Proceedings of the Fault Tolerant Computing Symposium", at pages 28 to 35, June 1989. The heuristic itself attempts to solve an NP-hard problem, i.e. computing the minimum-cost feedback-vertex set of a graph. Cheng and Agrawal proposed an approximation to the minimum-feedback vertex set problem in which flip-flops are selected based on the number of loops passing through them.
Since it was first proposed, loop breaking as a way of selecting flip-flops has become widely popular and several extensions to the approximate algorithm method of Cheng and Agrawal have been proposed. The teaching in an article by D. Lee and M. Reddy entitled "On Determining Scan Flip-Flops in Partial-Scan Designs" in the Proceedings of the International Conference on Computer-Aided Design, at pages 332-325 dated November 1990 and in an article by S. Park and S. Akers entitled "A Graph Theoretic Approach to Partial Scan Design by K-Cycle Elimination" in the Proceedings of the International Test Conference at pages 303 to 311 dated October 1992, was to improve the solution by first reducing the graph using techniques previously published in graph theory literature and then applying the approximate algorithm on the reduced graph. The teaching in an article by V. Chickermane and J. Patel entitled "An Optimization Based Approach to the Partial Scan Design Problem" in the Proceedings of the International Test Conference at pages 371 to 386 dated October 1990 and in an article by V. Chickermane and J. Patel entitled "A Fault Oriented Partial Scan Design Approach" in the Proceedings of the International Conference on Computer-Aided Design at pages 400 to 403 dated November 1991 was incorporating cost functions other than vertex cardinality into feedback vertex selection.
While the above approximations to the minimum feedback vertex set problem provide reasonably good results for the commonly available benchmarks, there are three problems associated with the approximations: how close to optimal the final solution is, is unclear; the enumeration of the potentially exponentially large number of cycles in the graph is involved; and optimization under any criterion other than the quantity of flip flops is not effective.